Search Results

Documents authored by Aspnes, James

Document
Complete Volume
DOI: 10.4230/LIPIcs.SAND.2022
LIPIcs, Volume 221, SAND 2022, Complete Volume

Authors: James Aspnes and Othon Michail

Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)

Abstract
LIPIcs, Volume 221, SAND 2022, Complete Volume
Cite as

1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 1-370, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Proceedings{aspnes_et_al:LIPIcs.SAND.2022,
  title =	{{LIPIcs, Volume 221, SAND 2022, Complete Volume}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{1--370},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022},
  URN =		{urn:nbn:de:0030-drops-159412},
  doi =		{10.4230/LIPIcs.SAND.2022},
  annote =	{Keywords: LIPIcs, Volume 221, SAND 2022, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.SAND.2022.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: James Aspnes and Othon Michail

Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 0:i-0:xvi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{aspnes_et_al:LIPIcs.SAND.2022.0,
  author =	{Aspnes, James and Michail, Othon},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{0:i--0:xvi},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.0},
  URN =		{urn:nbn:de:0030-drops-159426},
  doi =		{10.4230/LIPIcs.SAND.2022.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2020.19
Approximate Majority with Catalytic Inputs

Authors: Talley Amir, James Aspnes, and John Lazarsfeld

Published in: LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)

Abstract
Population protocols [Dana Angluin et al., 2006] are a class of algorithms for modeling distributed computation in networks of finite-state agents communicating through pairwise interactions. Their suitability for analyzing numerous chemical processes has motivated the adaptation of the original population protocol framework to better model these chemical systems. In this paper, we further the study of two such adaptations in the context of solving approximate majority: persistent-state agents (or catalysts) and spontaneous state changes (or leaks). Based on models considered in recent protocols for populations with persistent-state agents [Bartlomiej Dudek and Adrian Kosowski, 2018; Alistarh et al., 2017; Dan Alistarh et al., 2020], we assume a population with n catalytic input agents and m worker agents, and the goal of the worker agents is to compute some predicate over the states of the catalytic inputs. We call this model the Catalytic Input (CI) model. For m = Θ(n), we show that computing the parity of the input population with high probability requires at least Ω(n²) total interactions, demonstrating a strong separation between the CI model and the standard population protocol model. On the other hand, we show that the simple third-state dynamics [Angluin et al., 2008; Perron et al., 2009] for approximate majority in the standard model can be naturally adapted to the CI model: we present such a constant-state protocol for the CI model that solves approximate majority in O(n log n) total steps with high probability when the input margin is Ω(√{n log n}). We then show the robustness of third-state dynamics protocols to the transient leaks events introduced by [Alistarh et al., 2017; Dan Alistarh et al., 2020]. In both the original and CI models, these protocols successfully compute approximate majority with high probability in the presence of leaks occurring at each step with probability β ≤ O(√{n log n}/n). The resilience of these dynamics to leaks exhibits similarities to previous work involving Byzantine agents, and we define and prove a notion of equivalence between the two.
Cite as

Talley Amir, James Aspnes, and John Lazarsfeld. Approximate Majority with Catalytic Inputs. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{amir_et_al:LIPIcs.OPODIS.2020.19,
  author =	{Amir, Talley and Aspnes, James and Lazarsfeld, John},
  title =	{{Approximate Majority with Catalytic Inputs}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{19:1--19:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-176-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{184},
  editor =	{Bramas, Quentin and Oshman, Rotem and Romano, Paolo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.19},
  URN =		{urn:nbn:de:0030-drops-135040},
  doi =		{10.4230/LIPIcs.OPODIS.2020.19},
  annote =	{Keywords: population protocols, approximate majority, catalysts, leaks, lower bound}
}
Document
DOI: 10.4230/LIPIcs.DISC.2020.6
Message Complexity of Population Protocols

Authors: Talley Amir, James Aspnes, David Doty, Mahsa Eftekhari, and Eric Severson

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract
The standard population protocol model assumes that when two agents interact, each observes the entire state of the other. We initiate the study of message complexity for population protocols, where an agent’s state is divided into an externally-visible message and externally-hidden local state. We consider the case of O(1) message complexity. When time is unrestricted, we obtain an exact characterization of the stably computable predicates based on the number of internal states s(n): If s(n) = o(n) then the protocol computes semilinear predicates (unlike the original model, which can compute non-semilinear predicates with s(n) = O(log n)), and otherwise it computes a predicate decidable by a nondeterministic O(n log s(n))-space-bounded Turing machine. We then introduce novel O(polylog(n)) expected time protocols for junta/leader election and general purpose broadcast correct with high probability, and approximate and exact population size counting correct with probability 1. Finally, we show that the main constraint on the power of bounded-message-size protocols is the size of the internal states: with unbounded internal states, any computable function can be computed with probability 1 in the limit by a protocol that uses only 1-bit messages.
Cite as

Talley Amir, James Aspnes, David Doty, Mahsa Eftekhari, and Eric Severson. Message Complexity of Population Protocols. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 6:1-6:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{amir_et_al:LIPIcs.DISC.2020.6,
  author =	{Amir, Talley and Aspnes, James and Doty, David and Eftekhari, Mahsa and Severson, Eric},
  title =	{{Message Complexity of Population Protocols}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{6:1--6:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.6},
  URN =		{urn:nbn:de:0030-drops-130848},
  doi =		{10.4230/LIPIcs.DISC.2020.6},
  annote =	{Keywords: population protocol, message complexity, space-optimal}
}
Document
DOI: 10.4230/LIPIcs.DISC.2019.1
Consensus with Max Registers

Authors: James Aspnes and He Yang Er

Published in: LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)

Abstract
We consider the problem of implementing randomized wait-free consensus from max registers under the assumption of an oblivious adversary. We show that max registers solve m-valued consensus for arbitrary m in expected O(log^* n) steps per process, beating the Omega(log m/log log m) lower bound for ordinary registers when m is large and the best previously known O(log log n) upper bound when m is small. A simple max-register implementation based on double-collect snapshots translates this result into an O(n log n) expected step implementation of m-valued consensus from n single-writer registers, improving on the best previously-known bound of O(n log^2 n) for single-writer registers.
Cite as

James Aspnes and He Yang Er. Consensus with Max Registers. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 1:1-1:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{aspnes_et_al:LIPIcs.DISC.2019.1,
  author =	{Aspnes, James and Er, He Yang},
  title =	{{Consensus with Max Registers}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{1:1--1:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-126-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{146},
  editor =	{Suomela, Jukka},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.1},
  URN =		{urn:nbn:de:0030-drops-113088},
  doi =		{10.4230/LIPIcs.DISC.2019.1},
  annote =	{Keywords: consensus, max register, single-writer register, oblivious adversary, shared memory}
}
Document
DOI: 10.4230/LIPIcs.DISC.2018.8
Allocate-On-Use Space Complexity of Shared-Memory Algorithms

Authors: James Aspnes, Bernhard Haeupler, Alexander Tong, and Philipp Woelfel

Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)

Abstract
Many fundamental problems in shared-memory distributed computing, including mutual exclusion [James E. Burns and Nancy A. Lynch, 1993], consensus [Leqi Zhu, 2016], and implementations of many sequential objects [Prasad Jayanti et al., 2000], are known to require linear space in the worst case. However, these lower bounds all work by constructing particular executions for any given algorithm that may be both very long and very improbable. The significance of these bounds is justified by an assumption that any space that is used in some execution must be allocated for all executions. This assumption is not consistent with the storage allocation mechanisms of actual practical systems. We consider the consequences of adopting a per-execution approach to space complexity, where an object only counts toward the space complexity of an execution if it is used in that execution. This allows us to show that many known randomized algorithms for fundamental problems in shared-memory distributed computing have expected space complexity much lower than the worst-case lower bounds, and that many algorithms that are adaptive in time complexity can also be made adaptive in space complexity. For the specific problem of mutual exclusion, we develop a new algorithm that illustrates an apparent trade-off between low expected space complexity and low expected RMR complexity. Whether this trade-off is necessary is an open problem. For some applications, it may be helpful to pay only for objects that are updated, as opposed to those that are merely read. We give a data structure that requires no space to represent objects that are not updated at the cost of a small overhead on those that are.
Cite as

James Aspnes, Bernhard Haeupler, Alexander Tong, and Philipp Woelfel. Allocate-On-Use Space Complexity of Shared-Memory Algorithms. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 8:1-8:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{aspnes_et_al:LIPIcs.DISC.2018.8,
  author =	{Aspnes, James and Haeupler, Bernhard and Tong, Alexander and Woelfel, Philipp},
  title =	{{Allocate-On-Use Space Complexity of Shared-Memory Algorithms}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  pages =	{8:1--8:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Schmid, Ulrich and Widder, Josef},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.8},
  URN =		{urn:nbn:de:0030-drops-97974},
  doi =		{10.4230/LIPIcs.DISC.2018.8},
  annote =	{Keywords: Space complexity, memory allocation, mutual exclusion}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.OPODIS.2017
LIPIcs, Volume 95, OPODIS'17, Complete Volume

Authors: James Aspnes, Alysson Bessani, Pascal Felber, and João Leitão

Published in: LIPIcs, Volume 95, 21st International Conference on Principles of Distributed Systems (OPODIS 2017)

Abstract
LIPIcs, Volume 95, OPODIS'17, Complete Volume
Cite as

21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Proceedings{aspnes_et_al:LIPIcs.OPODIS.2017,
  title =	{{LIPIcs, Volume 95, OPODIS'17, Complete Volume}},
  booktitle =	{21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-061-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{95},
  editor =	{Aspnes, James and Bessani, Alysson and Felber, Pascal and Leit\~{a}o, Jo\~{a}o},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2017},
  URN =		{urn:nbn:de:0030-drops-86786},
  doi =		{10.4230/LIPIcs.OPODIS.2017},
  annote =	{Keywords: Distributed Systems, Performance of Systems, Concurrent Programming, Data Structures, Modes of Computation}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.OPODIS.2017.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: James Aspnes, Alysson Bessani, Pascal Felber, and João Leitão

Published in: LIPIcs, Volume 95, 21st International Conference on Principles of Distributed Systems (OPODIS 2017)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, pp. 0:i-0:xx, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{aspnes_et_al:LIPIcs.OPODIS.2017.0,
  author =	{Aspnes, James and Bessani, Alysson and Felber, Pascal and Leit\~{a}o, Jo\~{a}o},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
  pages =	{0:i--0:xx},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-061-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{95},
  editor =	{Aspnes, James and Bessani, Alysson and Felber, Pascal and Leit\~{a}o, Jo\~{a}o},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2017.0},
  URN =		{urn:nbn:de:0030-drops-86236},
  doi =		{10.4230/LIPIcs.OPODIS.2017.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2016.13
Time and Space Optimal Counting in Population Protocols

Authors: James Aspnes, Joffroy Beauquier, Janna Burman, and Devan Sohier

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Abstract
This work concerns the general issue of combined optimality in terms of time and space complexity. In this context, we study the problem of (exact) counting resource-limited and passively mobile nodes in the model of population protocols, in which the space complexity is crucial. The counted nodes are memory-limited anonymous devices (called agents) communicating asynchronously in pairs (according to a fairness condition). Moreover, we assume that these agents are prone to failures so that they cannot be correctly initialized. This study considers two classical fairness conditions, and for each we investigate the issue of time optimality of counting given the optimal space per agent. In the case of randomly interacting agents (probabilistic fairness), as usual, the convergence time is measured in terms of parallel time (or parallel interactions), which is defined as the number of pairwise interactions until convergence, divided by n (the number of agents). In case of weak fairness, where it is only required that every pair of agents interacts infinitely often, the convergence time is defined in terms of non-null transitions, i.e, the transitions that affect the states of the interacting agents. First, assuming probabilistic fairness, we present a "non-guessing" time optimal protocol of O(n log n) expected time given an optimal space of only one bit, and we prove the time optimality of this protocol. Then, for weak fairness, we show that a space optimal (semi-uniform) solution cannot converge faster than in big-omega (2^n) time (non-null transitions). This result, together with the time complexity analysis of an already known space optimal protocol, shows that it is also optimal in time (given the optimal space constrains).
Cite as

James Aspnes, Joffroy Beauquier, Janna Burman, and Devan Sohier. Time and Space Optimal Counting in Population Protocols. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{aspnes_et_al:LIPIcs.OPODIS.2016.13,
  author =	{Aspnes, James and Beauquier, Joffroy and Burman, Janna and Sohier, Devan},
  title =	{{Time and Space Optimal Counting in Population Protocols}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{13:1--13:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.13},
  URN =		{urn:nbn:de:0030-drops-70828},
  doi =		{10.4230/LIPIcs.OPODIS.2016.13},
  annote =	{Keywords: networks of passively mobile agents/sensors, population protocols, counting, anonymous non-initialized agents, time and space complexity, lower bounds}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact